package com.longge;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-04-25 02:18
 */
public class IsConnected {
    //有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
    //
    //省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
    //

    /**
     * 1 1 0
     * 1 1 0
     * 0 0 1
     */

    public int findCircleNum(int[][] isConnected) {
        int m = isConnected.length;
        if (m == 0) return 0;
        int n = isConnected[0].length;
        UF uf = new UF(m);
        for (int i = 0; i < m; i++) {
            for (int j = i+1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i,j);

                }
            }
        }
        return uf.count();
    }

    public static void main(String[] args) {
        new IsConnected().findCircleNum(new int[][]{{1,1,0},{1,1,0},{0,0,1}});

        UF uf = new UF(9);
        uf.union(0,3);
        uf.union(3,0);
    }
}
